package com.github.hgkmail.hello.leetcode101.greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class LC763PartitionLabels {
    public List<Integer> partitionLabels(String s) {
        //base case
        if (s.length()<=0) {
            return new ArrayList<>();
        }
        //统计第一次出现和最后一次出现的位置
        int[][] positions=new int[26][2];
        for (int i = 0; i < 26; i++) {
            //first come
            positions[i][0]=-1;
            //last come
            positions[i][1]=-1;
        }
        int alpha=0;
        for (int i = 0; i < s.length(); i++) {
            alpha = s.charAt(i)-'a';
            if (positions[alpha][0]<0) {
                positions[alpha][0]=positions[alpha][1]=i;
            } else {
                positions[alpha][1]=i;
            }
        }
        //切分字符串
        List<int[]> part=new ArrayList<>();
        int curr=0;
        while (curr<s.length()) {
            int a=s.charAt(curr)-'a';
            int end = positions[a][1];
            for (int i = curr; i < end; i++) {
                int b=s.charAt(i)-'a';
                if (positions[b][1]>end)  {
                    end=positions[b][1];
                }
            }
            part.add(new int[]{curr, end});
            curr=end+1;
        }

        return part.stream().map(arr->arr[1]-arr[0]+1).collect(Collectors.toList());
    }

    public static void main(String[] args) {

    }
}
